package com.learn.algorithm.graph;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class LeetCode127 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 总单词表
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) {
            return 0;
        }
        // 数量小的一侧
        Set<String> smallLevel = new HashSet<>();
        // 数量大的一侧
        Set<String> bigLevel = new HashSet<>();
        // 由小的一侧扩展出的下一层列表
        Set<String> nextLevel = new HashSet<>();

        smallLevel.add(beginWord);
        bigLevel.add(endWord);
        for (int len = 2; !smallLevel.isEmpty(); len++) {
            for (String w : smallLevel) {
                char[] word = w.toCharArray();
                for (int j = 0; j < word.length; j++) {
                    // 每个字符都试
                    char old = word[j];
                    for (char change = 'a'; change <= 'z'; change++) {
                        if (change != old) {
                            word[j] = change;
                            String next = String.valueOf(word);
                            if (bigLevel.contains(next)) {
                                return len;
                            }
                            if (dict.contains(next)) {
                                dict.remove(next);
                                nextLevel.add(next);
                            }
                        }
                    }
                    word[j] = old;
                }
            }
            if (nextLevel.size() <= bigLevel.size()) {
                Set<String> tmp = smallLevel;
                smallLevel = nextLevel;
                nextLevel = tmp;
            } else {
                Set<String> tmp = smallLevel;
                smallLevel = bigLevel;
                bigLevel = nextLevel;
                nextLevel = tmp;
            }
            nextLevel.clear();
        }
        return 0;
    }
}
